Find an Item - Educational Content

While insertion and deletion required $O(n)$ time due to mandatory traversal to a specific index $i$, searching for an item requires a similar linear approach.

To locate a node containing a specific target value (x), we must perform a sequential comparison starting from the head of the list.
This search operation is known as a linear search in the context of linked lists.
We use a pointer, $p$, to iterate through each node until a match is found or the list terminates ($\text{NULL}$).
The process involves checking the current node, and if no match, moving to the next node via the pointer.

Complexity Analysis: Find an Item

Time Complexity: $O(n)$

In the worst-case scenario, we must visit all $n$ nodes (if the item is at the end or not present).

Space Complexity: $O(1)$

Fixed space is used only for the temporary pointer $p$.

Key Takeaway: Unlike arrays where random access can locate an item in $O(1)$ if the index is known, linked lists must be traversed linearly to find either a position or a value.

1class Node: 2 # Reusing Node_Structure: {value, next} 3 def __init__(self, value, next_node=None): 4 self.value = value 5 self.next = next_node 6 7def find_item(head, target_value): 8 p = head # Start traversal using pointer p 9 index = 0 10 11 # Traverse until p is NULL (end of list) 12 while p is not None: 13 # Check if the current node's value matches the target 14 if p.value == target_value: 15 return (p, index) # Item found: return the node and index 16 17 p = p.next 18 index += 1 19 20 # Item not found 21 return (None, -1) 22 23# Setup list: 10 -> 20 -> 30 -> 40 24head_ex = Node(10, Node(20, Node(30, Node(40)))) 25 26# Search for 30 27found_node, found_index = find_item(head_ex, 30) 28print(f"Item 30 found at index: {found_index}") 29 30# Search for 50 (not present) 31not_found_node, not_found_index = find_item(head_ex, 50) 32print(f"Item 50 found at index: {not_found_index}")